package com.example;

/**
 * @Author loubobooo
 * @Description #152. 乘积最大子数组
 * @Date 2022/2/23
 */
public class MaximumProductSubarray {

    /**
     * 方法描述:给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     * 测试用例的答案是一个32-位 整数。
     * 子数组 是数组的连续子序列。
     *
     * 示例 1:
     * 输入: nums = [2,3,-2,4]
     * 输出: 6
     * 解释:子数组 [2,3] 有最大乘积 6。
     * @param: [nums]
     * @return: int
     * @author: loubobooo
     * @date: 2022/2/25
     */
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] dpMax = new int[length];
        int[] dpMin = new int[length];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int res = nums[0];
        //dpMax[i] dpMin[i]表示以nums[i]为结尾的最大最小值
        for (int i = 1; i < length; i++) {
            dpMax[i] = Math.max(dpMax[i - 1] * nums[i], Math.max(nums[i], dpMin[i - 1] * nums[i]));
            dpMin[i] = Math.min(dpMin[i - 1] * nums[i], Math.min(nums[i], dpMax[i - 1] * nums[i]));
            res = Math.max(res, Math.max(dpMax[i], dpMin[i]));
        }
        return res;
    }
}
